package cn.handong.tool.algorithm;

public class Rainwater {

    public int trap(int[] height){
        int sum = 0;
        int max = getMax(height);
        for (int i = 1; i < max; i++) {
            boolean isStart = false;
            int temp_sum = 0;
            for (int j = 0; j < height.length; j++) {
                if (isStart && height[j] < i){
                    temp_sum++;
                }
                if (height[j] >= i){
                    sum = sum + temp_sum;
                    temp_sum = 0;
                    isStart = true;
                }
            }
        }
        return sum;

    }

    private int getMax(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > max) max = height[i];
        }
        return max;
    }



    // 接雨水问题
    public int trap2(int[] height){
        int n = height.length;
        if (n == 0) return 0;
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1],height[i]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.min(leftMax[i],rightMax[i]) - height[i];
        }
        return res;
    }

    ////////

    public Integer getMaxArea(char[][] grid){
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    res = Math.max(res,bfs(grid,i,j));
                }
            }
        }
        return res;
    }
    public int bfs(char[][] grid, int i, int j){
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
            return 0;
        }
        grid[i][j] = '0';
        return bfs(grid, i - 1, j) + bfs(grid, i + 1 ,j) + bfs(grid, i, j - 1) + bfs(grid, i, j + 1) + 1;
    }



    public static int[] getNums(int[] nums){
        int[] indexArray = new int[5];
        for (int num : nums) {
            indexArray[num]++;
        }
        int index = 0;
        for (int i = 0; i < indexArray.length; i++) {
            while (indexArray[i] > 0){
                nums[index++] = i;
                indexArray[i]--;
            }
        }
        return nums;
    }

    public static void main(String[] args) {
//        int[] nums = getNums(new int[]{3,0,1});
//        for (int i = 0; i < nums.length; i++) {
//            System.out.println(nums[i]);
//        }

        /**
         *  ["1","1","1","1","0"],
         *   ["1","1","0","1","0"],
         *   ["1","1","0","0","0"],
         *   ["0","0","1","0","0"]
         *
         *
         *    ["1","1","0","0","0"],
         *   ["1","1","0","0","0"],
         *   ["0","0","1","0","1"],
         *   ["0","0","0","1","1"]
         * ]
         */

        char[][] grid = {{'1','1','0','0','0'},
                         {'1','1','0','0','0'},
                         {'0','0','1','0','1'},
                         {'0','0','0','1','1'}};
        int islandNum = getIslandNum(grid);
        System.out.println(islandNum);

    }


    public static int getIslandNum(char[][] grid){
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1'){
                    res++;
                    bfs1(grid,i,j);
                }
            }
        }
        return res;
    }

    public static void bfs1(char[][] grid, int i, int j){
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        grid[i][j] = '0';
        bfs1(grid,i+1,j);
        bfs1(grid,i-1,j);
        bfs1(grid,i,j+1);
        bfs1(grid,i,j-1);
    }





}
